Week 6
- Graphs are arguably the most important object in discrete
mathematics. A huge number of problems from computer science and combinator ics can be modelled in the language of graphs. This module introduces the basic notions of graph theory- graphs, cycles, paths, degree, isomorphism.
Basic Notions and Examples
So we have this board, 4×4 board and we have 15 tiles which are placed on this board and now you can move them. You can. for example, move the number 6 into the empty space, and then you can move tile number 11 up, and of course you can make everything in reverse. You can move the 11 back where it come from.
so how does that define a graph? Let's see.
Every possibility how to arrange the tiles on this four by four square will be a vertex. So here I only show you three vertices but i s of course many more vertices. And what is an edge. Well let's say two configurations are connected by an- edge if they are one move apart.
There are some classes of graphs that appear over and over again. And we just have to go through them quickly and introduce the names. Such that you understand, in the future when I refer to them.
The first important class of graphs, are the so called, complete graphs.
Graph Isomorphism, Degree, Graph Score
Isomorphism degree
A question: when are two graphs the same?